# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque


class Solution(object):
  def averageOfLevels(self, root):
    """
    :type root: TreeNode
    :rtype: List[float]
    """
    ans = []
    queue = deque([root])
    while queue:
      s = 0
      n = len(queue)
      for _ in range(n):
        top = queue.popleft()
        s += top.val
        if top.left:
          queue.append(top.left)
        if top.right:
          queue.append(top.right)
      ans.append(float(s) / n)
    return ans
